package com.cuz.for2024;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T15 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        for (int first = 0; first < nums.length; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = nums.length - 1;
            for (int second = first + 1; second < third; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third) {
                    int sum = nums[third] + nums[first] + nums[second];
                    if (sum > 0) {
                        third--;
                        continue;
                    }
                    if (sum == 0) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        ans.add(list);
                    }
                    break;
                }

            }

        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new T15().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}
